package dynamic;


import java.util.*;

import org.junit.Test;

public class Ex279 {
    
    //完全平方数最少
    class Solution {
        //动态规划，轻松解决
        public int numSquares1(int n) {
            int[] f = new int[n + 1];
            f[1] = 1; //1只有自身
            for (int i = 2; i <= n; i++) {
                int min = i - 1;
                for (int j = 1; j * j <= i; j++) {
                    min = Math.min(f[i - j * j], min);
                }
                f[i] = min + 1;
            }

            return f[n];
        }

        //BFS解法
        public int numSquares2(int n) {
           Queue<int[]> queue = new LinkedList<>();
            queue.offer(new int[]{n, 0});
            int[] cur;
            int res = n; //最大为n个1
            int[] visited = new int[n + 1];
            while (!queue.isEmpty()) {
                cur = queue.poll();
                for (int i = 1; i * i <= cur[0]; i++) {
                    if (visited[cur[0] - i * i] < 0) continue;
                    int[] newCur = new int[2];
                    newCur[0] = cur[0] - i * i;
                    newCur[1] = cur[1] + 1;
                    queue.add(newCur);
                    visited[cur[0] - i * i] = -1;
                    if (newCur[0] == 0) {
                        res = Math.min(res, newCur[1]);
                    }
                }
            }
            return res;
         }

         public int[] p;
         public int numSquares(int n) {
            p = new int[n + 1];
            return dfs(n);
         }

         public int dfs (int n) {
            if (p[n] != 0) return p[n];
            // if (map.containsKey(n)) return map.get(n);
            if (n == 0) return 0;
            int count = Integer.MAX_VALUE;

            for (int i = 1; i * i <= n; i++) {
                count = Math.min(count, dfs(n - i * i) + 1);
            }

            p[n] = count;
            // map.put(n, count);
            return count;
         }
    }

    @Test 
    public void test() {
        Solution s = new Solution();
        System.out.println(s.numSquares(5));
        System.out.println(s.numSquares(12));
        System.out.println(s.numSquares(13));
        System.out.println(s.numSquares(1000));

        System.out.println(s.numSquares(4000));
   

    }
}
